package me.algo.coll2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author guozheng
 * @date 2024/5/8
 */
public class C1 {

    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        set.insert(0);
        set.insert(1);
        set.remove(0);
        set.insert(2);
        set.remove(1);
        int random = set.getRandom();

    }
}

/**
 * https://leetcode.cn/problems/insert-delete-getrandom-o1/solutions/1411578/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-su-rlz2/?envType=study-plan-v2&envId=top-interview-150
 */
class RandomizedSet {

    private Map<Integer, Integer> mp;
    private List<Integer> lst;


    public RandomizedSet() {
        mp = new HashMap<>();
        lst = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (mp.containsKey(val)) {
            return false;
        }
        int size = lst.size();
        lst.addLast(val);
        mp.put(val, size);
        return true;
    }

    public boolean remove(int val) {
        if (!mp.containsKey(val)) {
            return false;
        }
        Integer idx = mp.get(val);
        int size = lst.size();
        Integer lastElement = lst.get(size - 1);
        lst.set(idx, lastElement);
        mp.put(lastElement, idx);
        lst.remove(size - 1);
        mp.remove(val);
        return true;
    }

    public int getRandom() {
        int i = ThreadLocalRandom.current().nextInt(lst.size());
        return lst.get(i);
    }

}
